// https://www.lintcode.com/problem/interleaving-positive-and-negative-numbers/

public class Solution {
    /*
     * @param A: An integer array.
     * @return: nothing
     */
    public void rerange(int[] A) {
        // write your code here
        // 先分区，负数再前，正数在后。
        int start = 0;
        int end = A.length - 1;
        while (start < end) {
            while ((start < end) && (A[start] < 0)) {
                ++start;
            }
            while ((start < end) && (A[end] > 0)) {
                --end;
            }
            if (start < end) {
                swap(A, start, end);
            }
        }
        int cp = 0;
        int cn = 0;
        for (int a : A) {
            if (a > 0) {
                ++cp;
            } else {
                ++cn;
            }
        }
        start = 0;
        end = A.length - 1;
        if (cn > cp) {
            ++start;
        } else if (cn < cp) {
            --end;
        }
        while (start < end) {
            swap(A, start, end);
            start += 2;
            end -= 2;
        }
    }

    protected void swap(int[] A, int i, int j) {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
}